package com.dubious.interview.euler;

import java.util.LinkedList;
import java.util.List;

import com.dubious.interview.euler.pandigital.PandigitalNumbers;

public class Problem38 {

    /**
     * Take the number 192 and multiply it by each of 1, 2, and 3:
     * 
     * 192 x 1 = 192
     * 192 x 2 = 384
     * 192 x 3 = 576
     * 
     * By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 
     * 192384576 the concatenated product of 192 and (1,2,3)
     * 
     * The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, 
     * giving the pandigital, 918273645, which is the concatenated product of 9 and 
     * (1,2,3,4,5).
     * 
     * What is the largest 1 to 9 pandigital 9-digit number that can be formed as the 
     * concatenated product of an integer with (1,2, ... , n) where n > 1?
     */
    public static long run(int ceiling)
    {
        // strategy: iterate down from the ceiling through all 1 to 9 pandigital numbers and
        // check if it can be created as a concatenated product as specified
        for(Long pandigitalNumber : new PandigitalNumbers(1, 9, ceiling))
        {
            if(isConcatenatedProduct(pandigitalNumber))
            {
                return pandigitalNumber;
            }
        }
        
        throw new RuntimeException("Result Not Found");
    }
    
    private static boolean isConcatenatedProduct(long value)
    {
        // break up the number into its digits
        List<Integer> digits = Utilities.extractDigits(value);
        
        // try different possibilities of concatenation
        for(int i = 0; i <= digits.size()/2; i++)
        {
            // will build a set of digits for comparison purposes
            List<Integer> concatDigits = new LinkedList<Integer>();
            // search for a candidate as the root of the concatenation
            long rootMultiplicand = Utilities.getSubNumber(digits, 0, i);
            concatDigits.addAll(Utilities.extractDigits(rootMultiplicand));
            
            // in a loop build the concatenation
            int stepMultiplicand = 2;
            while(concatDigits.size() < digits.size())
            {
                concatDigits.addAll(Utilities.extractDigits(rootMultiplicand * stepMultiplicand));
                stepMultiplicand++;
            }
            
            if(digits.equals(concatDigits))
            {
                return true;
            }
        }
        
        return false;
    }
    
    public static void outputPandigitalNumbers()
    {
        for(Long pandigitalNumber : new PandigitalNumbers(1, 9, 987654321))
        {
            System.out.println(pandigitalNumber);
        }
    }
    
    /*
    public static void outputPandigitalNumbersScratch()
    {
        // try to implement a way that allows output of one number to each call
        List<Integer> setDigits = new LinkedList<Integer>();
        List<Integer> remainingDigits = new LinkedList<Integer>(asList(9, 8, 7, 6, 5, 4, 3, 2, 1));
        
        for(int i = 0; i <100; i++)
        {
            outputNextPandigitalNumber(setDigits, remainingDigits);
        }
    }
    
    private static void outputNextPandigitalNumber(List<Integer> setDigits, List<Integer> remainingDigits)
    {
        while(remainingDigits.size() > 0)
        {
            setDigits.add(remainingDigits.remove(0));
        }
        
        // have a pandigital number, output it
        System.out.println(setDigits);
        
        // clean up for next call
        // put numbers back into remainingDigits bucket, starting from end of setDigits as long
        // as digits are in decreasing value
        do
        {
            // this add preserves highest to lowest value in the remainingDigits
            remainingDigits.add(setDigits.remove(setDigits.size() - 1));
        } while(setDigits.get(setDigits.size() - 1) < remainingDigits.get(remainingDigits.size() - 1));
        
        // have reached a digit in setDigits that was not less than the digit after it
        // replace it with the highest remaining digit with lower value
        Integer swapDigit = setDigits.remove(setDigits.size() - 1);
        for(int i = 0; i < remainingDigits.size(); i++)
        {
            if(remainingDigits.get(i) < swapDigit)
            {
                setDigits.add(remainingDigits.get(i));
                remainingDigits.set(i, swapDigit);
                break;
            }
        }
    }
    
    public static void outputPandigitalNumbersScratch2()
    {
        // try to implement using recursive algorithm
        List<Integer> digits = Arrays.asList(9, 8, 7, 6, 5, 4, 3, 2, 1);
        
        recurseOutputPandigitalNumbers(new ArrayList<Integer>(0), digits);
    }
    
    private static void recurseOutputPandigitalNumbers(List<Integer> setDigits, List<Integer> remainingDigits)
    {
        if(remainingDigits.size() == 1)
        {
            // base case, we have a complete pandigital number
            List<Integer> newSetDigits = new ArrayList<Integer>(setDigits.size() + 1);
            newSetDigits.addAll(setDigits);
            newSetDigits.add(remainingDigits.get(0));
            
            System.out.println(newSetDigits);
        } else
        {
            for(int i = 0; i < remainingDigits.size(); i++)
            {
                List<Integer> newSetDigits = new ArrayList<Integer>(setDigits.size() + 1);
                newSetDigits.addAll(setDigits);
                newSetDigits.add(remainingDigits.get(i));
                
                List<Integer> newRemainingDigits = new ArrayList<Integer>(remainingDigits.size() - 1);
                newRemainingDigits.addAll(remainingDigits);
                newRemainingDigits.remove(i);
                
                recurseOutputPandigitalNumbers(newSetDigits, newRemainingDigits);
            }
        }
    }
    */
}
